Mathematical programming, or mathematical optimization, is the selection of a best element (with regard to some criteria) from some set of available alternatives. In the simplest case, an optimization problem consists of maximizing or minimizing a real function by systematically choosing input values from within an allowed set and computing the value of the function. More generally, optimization includes finding “best available” values of some objective function given a defined domain. The domain is often specified by a set of constraints, which are equalities or inequalities that the members of the domain have to satisfy.
Convex programming is one kind of mathematical programming that studies the case when the objective function is convex (minimization) or concave (maximization) and the constraint set is convex. This can be viewed as a particular case of nonlinear programming or as generalization of linear or convex quadratic programming. An important characteristic of convex programming is that a local optimum of a convex programming problem must be a global optimum. Therefore, convex programming guarantees the achievement of globally optimal solutions. Linear programming (LP) is a type of convex programming that studies the case in which the objective function is linear and the set of constraints is specified using only linear equalities and inequalities.
In mathematical optimization, the simplex algorithm (or simplex method) is a popular algorithm for solving linear programming problems, where there may be tens of thousands of constraints. The simplex method takes constraints, converts inequality constraints into equality constraints, and enters them into a tableau, which is a matrix representation whose rows initially correspond to the constraints. It then performs pivots on the tableau, which are a form of Gaussian elimination. To perform a pivot on a row, it solves for one of its variables, and then substitutes the resulting expression for that variable into the other rows.
The incremental simplex method is a modification of the simplex algorithm that starts with an existing solution to an existing linear programming problem, and then adds, removes, or modifies one or more constraints of the existing linear programming problem to produce a new problem, and arrives at a solution to the new problem more quickly than if it re-solved the new problem from scratch. It is called incremental, because small changes to the set of constraints can be handled with a proportionally small amount of additional work.
In the incremental simplex method, each constraint is given a special variable called a marker which is only ever present in that constraint. After pivots, the marker may appear in multiple rows in the tableau, which means the constraints have been “mixed in” to each other. To remove a constraint, it is first necessary to undo the pivoting operations, so the row once again reflects that constraint in its original form. This isolates the effects of the constraint into a single row. The row can then be removed from the tableau. Because of the undoing of the pivoting operations, the removal of a constraint can be computationally expensive.
The incremental simplex method is used to solve many different linear programming problems, some of which involves tens of thousands of constraints and the constraints are constantly changing. For example, the incremental simplex method can be used to compute the optimal layout of user interface (UI) controls of a graphical user interface (GUI) within a window or screen, where there are many constraints regarding the positions of the controls and these constraints are constantly changing as a user interacting with the GUI. In order to maintain a high level of responsiveness to user interactions, techniques for allowing more efficient and quicker removal of constraints are desirable.